"""哈希表"""

from collections import abc

from .bst import AVLTree


class HashTable:
    _UPPER_TOL = 10
    _LOWER_TOL = 2
    _capacity_index = 0
    __capacity = [53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
                  49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
                  12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741]

    def __init__(self):
        self.m = self.__capacity[self._capacity_index]
        self._hash_table = tuple(AVLTree() for _ in range(self.m))
        self._size = 0

    def _hash_code(self, key):
        return (hash(key) & 0x7fffffff) % self.m

    def _resize(self, k):
        new_table = tuple(AVLTree() for _ in range(k))
        self.m = k
        for i in self._hash_table:
            for key, val in i.pre_order():
                new_table[self._hash_code(key)].add(key, val)
        self._hash_table = new_table

    def __len__(self):
        return self._size

    def add(self, key, val):
        """增"""
        if not isinstance(key, abc.Hashable):
            raise KeyError("key of HashTable is not hashable.")
        hash_map = self._hash_table[self._hash_code(key)]
        if key in hash_map:
            hash_map.set(key, val)
        else:
            hash_map.add(key, val)
            self._size += 1
            if self._size >= self._UPPER_TOL * self.m \
                    and self._capacity_index < len(self.__capacity) - 1:
                self._capacity_index += 1
                self._resize(self.__capacity[self._capacity_index])

    def remove(self, key):
        """删"""
        if not isinstance(key, abc.Hashable):
            raise KeyError("key of HashTable is not hashable.")
        ret = None
        hash_map = self._hash_table[self._hash_code(key)]
        if key in hash_map:
            ret = hash_map.remove(key)
            self._size -= 1
            if self._size <= self._LOWER_TOL * self.m and self._capacity_index - 1 >= 0:
                self._capacity_index -= 1
                self._resize(self.__capacity[self._capacity_index])
        return ret

    def set(self, key, new_val):
        """改"""
        if not isinstance(key, abc.Hashable):
            raise KeyError("key of HashTable is not hashable.")
        hash_map = self._hash_table[self._hash_code(key)]
        if key not in hash_map:
            raise KeyError("Key does not exist.")
        hash_map.set(key, new_val)

    def __contains__(self, key):
        """查"""
        if not isinstance(key, abc.Hashable):
            raise KeyError("key of HashTable is not hashable.")
        hash_map = self._hash_table[self._hash_code(key)]
        return key in hash_map

    def get(self, key):
        """查"""
        if not isinstance(key, abc.Hashable):
            raise KeyError("key of HashTable is not hashable.")
        hash_map = self._hash_table[self._hash_code(key)]
        if key not in hash_map:
            raise KeyError("Key does not exist.")
        return hash_map.get(key)
